10948. Задача на простоту

Представить натуральное число n в виде суммы двух простых чисел p1 и p2. 

Вход. Каждая строка содержит одно число n (3 < n £ 10⁶). Последний тест содержит n = 0 и не обрабатывается.

Выход. Для каждого входного значения n вывести его разложение в виде суммы двух простых чисел в соответствии с приведенным ниже форматом. В случае существования нескольких разложений выводить следует то, которое максимизирует разницу между p₂ и p₁. Если число n нельзя представить в виде суммы двух простых чисел, то вывести сообщение “NO WAY!”.

Пример входа

4
5
6
7
9
10
11
0

Пример выхода

4:
2+2
5:
2+3
6:
3+3
7:
2+5
9:
2+7
10:
3+7
11:

NO WAY!

РЕШЕНИЕ

простые числа

Анализ алгоритма

При помощи решета Эратосфена сгенерируем массив primes, в котором primes[i] = 1 для простых i и primes[i] = 0 для составных i. Для каждого входного n ищем такую пару чисел (i, n – i), для которой i и n – i простые. Если такая пара найдена, то выводим ее. Если такой пары не существует, то выводим сообщение “NO WAY!”.

Пример

Для n = 10 существует два способа, которыми можно его представить в виде суммы двух простых чисел: 10 = 3 + 7, 10 = 5 + 5. Поскольку разница 7 – 3 больше чем 5 – 5, то выводим первый вариант.

Реализация алгоритма

При помощи решета Эратосфена сгенерируем массив primes для дальнейшего тестирования чисел на простоту. Поскольку n £ 10⁶, то положим длину массива MAX равной 1000001.

#define MAX 1000001

int primes[MAX];

void gen_primes(void)

{

int i, j;

for(i = 0; i < MAX; i++) primes[i] = 1;

for(i = 2; i <= (int)sqrt(1.0*MAX); i++)

if (primes[i])

for(j = i; j * i < MAX; j++) primes[i * j] = 0;

}

Функция FindSol(n) ищет пару простых чисел (p₁, p₂), для которой n = p₁ + p₂. Достаточно перебирать лишь такие пары (p₁, p₂), для которых p₁ < p₂. Откуда следует, что p₁ £ n/2. Когда встретится пара (i, n – i), для которой i и n – i простые (значение i перебирается от до 2 до n/2), то выводим ее и завершаем выполнение функции. Если требуемая пара (p₁, p₂) не встретилась, то выводим сообщение “NO WAY!”. Если у числа n существует несколько разложений, то при указанном способе поиска первой найденной парой (p₁, p₂) будет та, для которой разница p₂ – p₁ максимальна.

void FindSol(int n)

{

int i, res = 0;

printf("%d:\n",n);

for(i = 2; i <= n / 2; i++)

if (primes[i] && primes[n-i])

{

printf("%d+%d\n",i,n-i);

return;

}

printf("NO WAY!\n");

}

Основной цикл программы. Генерируем массив primes при помощи функции gen_primes. После чего для каждого входного значения n вызываем FindSol(n).

gen_primes();

while(scanf("%d",&n),n)

FindSol(n);